You are given an n x n integer matrix. You can do the following operation any number of times:
- Choose any two adjacent elements of
matrixand multiply each of them by-1.
Two elements are considered adjacent if and only if they share a border.
Your goal is to maximize the summation of the matrix's elements. Return the maximum sum of the matrix's elements using the operation mentioned above.
Input: matrix = [[1,-1],[-1,1]] Output: 4 Explanation: We can follow the following steps to reach sum equals 4: - Multiply the 2 elements in the first row by -1. - Multiply the 2 elements in the first column by -1.
Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]] Output: 16 Explanation: We can follow the following step to reach sum equals 16: - Multiply the 2 last elements in the second row by -1.
n == matrix.length == matrix[i].length2 <= n <= 250-105 <= matrix[i][j] <= 105
implSolution{pubfnmax_matrix_sum(matrix:Vec<Vec<i32>>) -> i64{letmut count_neg_even = true;letmut min_abs = i32::MAX;letmut ret = 0;for i in0..matrix.len(){for j in0..matrix.len(){if matrix[i][j] < 0{ count_neg_even = !count_neg_even;} min_abs = min_abs.min(matrix[i][j].abs()); ret += matrix[i][j].abs()asi64;}}if !count_neg_even { ret -= 2* min_abs asi64;} ret }}